Search for: All records

The Multi-Agent Path Finding (MAPF) is a problem of finding a plan for agents to reach their desired locations without colliding. Distributed Multi-Agent Path Finder (DMAPF) solves the MAPF problem by decomposing a given MAPF problem instance into smaller subproblems and solve them in parallel. DMAPF works in rounds. Between two consecutive rounds, agents may migrate between two adjacent subproblems following their abstract plans, which are pre-computed, until all of them reach the areas that contain their desired locations. Previous works on DMAPF compute an abstract plan for each agent without the knowledge of other agents’ abstract plans, resulting in high congestion in some areas, especially those that act as corridors. The congestion negatively impacts the runtime of DMAPF and prevents it from being able to solve dense MAPF problems. In this paper, we (i) investigate the use of Uniform-Cost Search to mitigate the congestion. Additionally, we explore the use of several other techniques including (ii) using timeout estimation to preemptively stop solving and relax a subproblem when it is likely to get stuck; (iii) allowing a solving process to manage multiple subproblems – aimed to increase concurrency; and (iv) integrating with MAPF solvers from the Conflict-Based Search family. Experimental results show that our new system is several times faster than the previous ones; can solve larger and denser problems that were unsolvable before; and has better runtime than PBS and EECBS, which are state-of-the-art centralized suboptimal MAPF solvers, in problems with a large number of agents. 

Autonomous robotic vehicles (i.e., drones) are potentially transformative for search and rescue (SAR). This paper works toward wearable interfaces, through which humans team with multiple drones. We introduce the Virtual Drone Search Game as a first step in creating a mixed reality simulation for humans to practice drone teaming and SAR techniques. Our goals are to (1) evaluate input modalities for the drones, derived from an iterative narrowing of the design space, (2) improve our mixed reality system for designing input modalities and training operators, and (3) collect data on how participants socially experience the virtual drones with which they work. In our study, 17 participants played the game with two input modalities (Gesture condition, Tap condition) in counterbalanced order. Results indicated that participants performed best with the Gesture condition. Participants found the multiple controls challenging, and future studies might include more training of the devices and game. Participants felt like a team with the drones and found them moderately agentic. In our future work, we will extend this testing to a more externally valid mixed reality game. 

Multi-Agent Path Finding (MAPF) problems are traditionally solved in a centralized manner. There are works focusing on completeness, optimality, performance, or a tradeoff between them. However, there are only a few works based on spatial distribution. In this paper, we introduce ros-dmapf, a distributed MAPF solver. It consists of multiple MAPF sub-solvers, which---besides solving their assigned sub-problems---interact with each other to solve a given MAPF problem. In the current implementation, the sub-solvers are answer set planning systems for multiple agents, and are created based on spatial distribution of the problem. Interactions between components of ros-dmapf are facilitated by the Robot Operating System (ROS). The highlights of ros-dmapf are its scalability and a high degree of parallelism. We empirically evaluate ros-dmapf using the move-only domain of the asprilo system and results suggest that ros-dmapf scales up well. For instance, ros-dmapf gives a solution of length around 600 for a MAPF problem with 2000 robots in randomly generated 100×100 obstacle-free maps---a problem beyond the capability of a single sub-solver---within 7 minutes on a consumer laptop. We also evaluate ros-dmapf against some other MAPF solvers and results show that the system performs well. We also discuss possible improvements for future work. 

The proliferation of unmanned aerial systems (i.e., drones) can provide great value to the future of search and rescue. However, with the increase adoption of such systems, issues around hybrid human-drone team coordination and planning will arise. To address these early challenges, we provide insights into the development of testbeds in the form of mixed reality games with simulated drones. This research presents an architecture to address challenges and opportunities in using drones for search and rescue. On this architecture, we develop a mixed reality game in which human players engage with the physical world and with gameplay that is purely virtual. We expect the architecture to be useful to a range of researchers an practitioners, forming the basis for investigating and training within this unique, new domain.